#include <iostream>
#include <vector>

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};

int getListLength(ListNode * head)
{
    if(head == nullptr)
    {
        return 0;
    }
    int count = 1;
    ListNode * cur = head;
    while(cur->next != nullptr)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

class Solution 
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        int lengthA = getListLength(headA);
        int lengthB = getListLength(headB);

        if(lengthA == 0 || lengthB == 0)
        {
            return nullptr;
        }

        if(lengthA < lengthB)
        {
            ListNode * temp = headA;
            headA = headB;
            headB = temp;
            int tempLength = lengthA;
            lengthA = lengthB;
            lengthB = tempLength;
        }

        int diff = lengthA - lengthB;
        ListNode _dummyHeadA(0, headA);
        ListNode _dummyHeadB(0, headB);
        ListNode * curA = &_dummyHeadA;
        ListNode * curB = &_dummyHeadB;
        for(int i = 0; i < diff; i++)
        {
            curA = curA->next;
        }

        while(curA != nullptr)
        {
            if(curA == curB)
            {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }

        return nullptr;
    }
};

// 创建链表辅助函数
ListNode* createList(const std::vector<int>& values) {
    if (values.empty()) return nullptr;
    
    ListNode* head = new ListNode(values[0]);
    ListNode* current = head;
    
    for (size_t i = 1; i < values.size(); ++i) {
        current->next = new ListNode(values[i]);
        current = current->next;
    }
    
    return head;
}

// 打印链表辅助函数
void printList(ListNode* head) {
    ListNode* current = head;
    while (current) {
        std::cout << current->val;
        if (current->next) std::cout << " -> ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 释放链表内存辅助函数
void freeList(ListNode* head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

int main() {
    Solution solution;
    
    // 测试案例1：两个链表相交于某一节点
    // 链表A: 4->1->8->4->5
    // 链表B: 5->0->1->8->4->5
    // 相交节点: 8
    ListNode* commonPart1 = createList({8, 4, 5});
    ListNode* headA1 = new ListNode(4, new ListNode(1, commonPart1));
    ListNode* headB1 = new ListNode(5, new ListNode(0, new ListNode(1, commonPart1)));
    
    std::cout << "测试案例1：" << std::endl;
    std::cout << "链表A: ";
    printList(headA1);
    std::cout << "链表B: ";
    printList(headB1);
    
    ListNode* intersection1 = solution.getIntersectionNode(headA1, headB1);
    if (intersection1) {
        std::cout << "相交节点值: " << intersection1->val << std::endl;
    } else {
        std::cout << "链表不相交" << std::endl;
    }
    std::cout << std::endl;
    
    // 测试案例2：两个链表不相交
    // 链表A: 1->2->3->4
    // 链表B: 5->6->7
    ListNode* headA2 = createList({1, 2, 3, 4});
    ListNode* headB2 = createList({5, 6, 7});
    
    std::cout << "测试案例2：" << std::endl;
    std::cout << "链表A: ";
    printList(headA2);
    std::cout << "链表B: ";
    printList(headB2);
    
    ListNode* intersection2 = solution.getIntersectionNode(headA2, headB2);
    if (intersection2) {
        std::cout << "相交节点值: " << intersection2->val << std::endl;
    } else {
        std::cout << "链表不相交" << std::endl;
    }
    std::cout << std::endl;
    
    // 测试案例3：两个链表相交于尾部节点
    // 链表A: 1->2->3
    // 链表B: 4->5->3
    // 相交节点: 3
    ListNode* commonNode3 = new ListNode(3);
    ListNode* headA3 = new ListNode(1, new ListNode(2, commonNode3));
    ListNode* headB3 = new ListNode(4, new ListNode(5, commonNode3));
    
    std::cout << "测试案例3：" << std::endl;
    std::cout << "链表A: ";
    printList(headA3);
    std::cout << "链表B: ";
    printList(headB3);
    
    ListNode* intersection3 = solution.getIntersectionNode(headA3, headB3);
    if (intersection3) {
        std::cout << "相交节点值: " << intersection3->val << std::endl;
    } else {
        std::cout << "链表不相交" << std::endl;
    }
    std::cout << std::endl;
    
    // 测试案例4：一个链表为空
    // 链表A: 1->2->3
    // 链表B: nullptr
    ListNode* headA4 = createList({1, 2, 3});
    ListNode* headB4 = nullptr;
    
    std::cout << "测试案例4：" << std::endl;
    std::cout << "链表A: ";
    printList(headA4);
    std::cout << "链表B: 空链表" << std::endl;
    
    ListNode* intersection4 = solution.getIntersectionNode(headA4, headB4);
    if (intersection4) {
        std::cout << "相交节点值: " << intersection4->val << std::endl;
    } else {
        std::cout << "链表不相交" << std::endl;
    }
    std::cout << std::endl;
    
    // 测试案例5：两个链表完全相同
    // 链表A: 1->2->3
    // 链表B: 1->2->3
    // 相交节点: 1
    ListNode* headA5 = createList({1, 2, 3});
    ListNode* headB5 = headA5; // 两个链表完全相同
    
    std::cout << "测试案例5：" << std::endl;
    std::cout << "链表A: ";
    printList(headA5);
    std::cout << "链表B: ";
    printList(headB5);
    
    ListNode* intersection5 = solution.getIntersectionNode(headA5, headB5);
    if (intersection5) {
        std::cout << "相交节点值: " << intersection5->val << std::endl;
    } else {
        std::cout << "链表不相交" << std::endl;
    }
    std::cout << std::endl;

    // 测试案例6：两个链表都是只有一个节点[1]，且相交
    // 链表A: 1
    // 链表B: 1
    // 相交节点: 1
    ListNode* headA6 = new ListNode(1);
    ListNode* headB6 = headA6; // 两个链表完全相同

    std::cout << "测试案例6：" << std::endl;
    std::cout << "链表A: ";
    printList(headA6);
    std::cout << "链表B: ";
    printList(headB6);

    ListNode* intersection6 = solution.getIntersectionNode(headA6, headB6);
    if (intersection6) {
        std::cout << "相交节点值: " << intersection6->val << std::endl;
    } else {
        std::cout << "链表不相交" << std::endl;
    }

    // 释放内存
    // 注意：对于相交的链表，我们需要避免重复释放相交部分
    freeList(headA1); // 这会释放commonPart1
    freeList(headB1->next->next); // 只释放B链表独有部分
    delete headB1->next;
    delete headB1;
    
    freeList(headA2);
    freeList(headB2);
    
    freeList(headA3); // 这会释放commonNode3
    delete headB3->next; // 只释放B链表独有部分
    delete headB3;
    
    freeList(headA4);

    freeList(headA5); // headB5指向相同的链表，所以只需释放一次

    freeList(headA6); // headB6指向相同的链表，所以只需释放一次
    
    return 0;
}
